package com.tgy.链表;

import java.util.Stack;

/***
 * @ClassName: SingleLinkedListDemo
 * @Description: 单链表实现
 * @Auther: tanggy3
 * @Date: 13:52 2022/6/20
 * @version : V1.0
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        aaa();
        SingleLinkedList list = new SingleLinkedList();
//        list.aiAdd(new Node(1, "1号"));
//        list.aiAdd(new Node(8, "8号"));
//        list.aiAdd(new Node(3, "3号"));
//        list.aiAdd(new Node(4, "4号"));
//        list.aiAdd(new Node(3, "3号"));
//        list.upd(new Node(9, "这是修改后的数据"));
//        list.show();
//        System.out.println("=========================");
//        list.del(new Node(8, "1号"));
//        list.show();
//        int i = list.currentSize();
//        System.out.println("数量为===>" + i);
//        Node node = list.getLastNodeByIndex1(2);
//        System.out.println(node);
//
//        System.out.println("===========");
//        showMe(resverNode(list.getNode()));
//
//
//        System.out.println("反转前=====");
//        showMe(list.getNode());
//
//        System.out.println("stack 反转===========");
//        showMe(resverNodeByStack(list.getNode()));


    }

    /**
     * 反转单链表方法一
     *
     * @param inNode
     * @return
     */
    public static Node resverNode(Node inNode) {
        //如果当前链表为空，或者只有一个节点，就直接返回
        if (inNode.nextNode == null || inNode.nextNode.nextNode == null) {
            return inNode;
        }
        Node temp = inNode.nextNode;
        Node next = null;
        Node reverseHead = new Node(0, "");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        while (temp != null) {
            /**
             * 1、将当前节点的下一个节点取出保存，为了循环使用
             * 2、将当前节点的下一个节点指向反转数组的第一个有效节点！！！！！
             * 4、然后将反转链表的第一个有效节点指向当前节点，完成前后调换！！！！！  这样就完成了把反转链表断开然后把当前节点插入最前面的操作了
             * 3、辅助节点后移
             */
            next = temp.nextNode;//先暂时保存当前节点的下一个节点，因为temp会被改变

            //将temp的下一个节点指向新的链表的最前端
            temp.nextNode = reverseHead.nextNode;
            //将temp 连接到新的链表上
            reverseHead.nextNode = temp;
            //让temp后移
            temp = next;


        }
        inNode.nextNode = reverseHead.nextNode;
        return reverseHead;
    }

    ;

    /**
     * 利用栈的方式反转链表
     *
     * @param inNode
     */
    public static Node resverNodeByStack(Node inNode) {

        //创建一个辅助栈
        Stack<Node> stack = new Stack<>();
        Node temp1 = inNode.nextNode;
        //遍历原始单链表，然后放入栈中
        while ((temp1 != null)) {
            stack.push(temp1);
            temp1 = temp1.nextNode;
        }
        /**
         * 这里直接引用这个对象，后面的变了前面的也会变
         */
        Node outNode = new Node();
        Node entry = outNode;
        while (!stack.isEmpty()) {
            //从栈里面取出一个元素，并把下一个节点置为空
            Node node = stack.pop();
            node.nextNode = null;
            /**
             * 把取出的节点接到下当前节点
             * 这一步特别重要，可以debug监视变量进行查看
             * 第一次进来的时候entry和outNode 指向的是一个对象，修改entry就会同步修改
             * a步骤 把栈里取出来的节点加搭到 共同对象的下一个节点
             * b步骤 把entry指向取出节点，相当于把entry变量 接到outNode的尾部
             * 然后重复a步骤，相当于延续entry，延续了entry后就相当于延续了outNode了  因为outNode的next就是entry
             * a步骤和b步骤共同完成了取出节点并接入outNode的尾部，然后还让entry在尾部
             */
            entry.nextNode = node;//a步骤
            entry = node;//b步骤
        }
        return outNode;
    }

    ;

    //展示链表
    public static void showMe(Node node) {
        Node temp = node;
        if (node.nextNode == null) {
            System.out.println("链表为空");
            return;
        }
        System.out.println(temp);
        while (temp.nextNode != null) {
            System.out.println(temp.nextNode);
            temp = temp.nextNode;
        }
    }


    static void aaa() {
        SingleLinkedList list = new SingleLinkedList();
        //list.add(new Node(1));
        list.add(new Node(2));
        //list.add(new Node(3));
        //list.add(new Node(4));
        showMe(list.getNode());
        System.out.println("============");
        showMe(swapNodes(list.getNode(), 2));


    }

    public static Node swapNodes(Node head, int k) {
        Node head1 = head;
        int sum = 1;
        while (head1.nextNode != null) {
            sum++;
            head1 = head1.nextNode;
        }
        int temp = 1;
        int per = 0;
        int tail = 0;
        Node head2 = head;
        Node head3 = head2;
        Node head4 = head2;
        for (int i = 1; i <= sum; i++) {
            if (temp == k) {
                per = head2.no;
            }
            if (temp == sum - k + 1) {
                tail = head2.no;
            }
            temp++;
            head2 = head2.nextNode;
        }


        int temp1 = 1;
        for (int i = 1; i <= sum; i++) {
            if (temp1 == k) {
                head3.no = tail;
            }
            if (temp1 == sum - k + 1) {
                head3.no = per;
            }
            temp1++;
            head3 = head3.nextNode;
        }

        return head4;
    }
}


//定义类管理节点
class SingleLinkedList {
    //初始化一个头节点
    private Node head = new Node(1, "");
    //添加节点,无顺序的

    /**
     * 1、找到当前链表的最后节点，
     * 2、将最后这个节点的next 指向这个新的节点
     */
    public void add(Node node) {
        /** 因为头节点不能动，所以需要一个零时变量来辅助 **/
        Node temp = head;
        while (temp.nextNode != null) {
            temp = temp.nextNode;
        }
        temp.nextNode = node;
    }

    //智能添加，按照数字顺序，如果有已经存在排名就报错
    public void aiAdd(Node node) {
        /** 因为头节点不能动，所以需要一个零时变量来辅助 **/
        Node temp = head;
        boolean flag = false;//编号是否存在
        while (temp.nextNode != null) {
            //满足条件就把node加到temp后面
            if (temp.nextNode.no > node.no) {
                //temp.nextNode= node;
                break;
            } else if (temp.nextNode.no == node.no) {
                flag = true;
                System.out.println("编号已经存在");
            }
            if (flag) break;
            temp = temp.nextNode;
        }
        if (!flag) {
            node.nextNode = temp.nextNode;
            temp.nextNode = node;
        }

    }

    //遍历单链表
    public void show() {
        Node temp = head;
        if (head.nextNode == null) {
            System.out.println("链表为空");
            return;
        }
        while (temp.nextNode != null) {
            temp = temp.nextNode;
            System.out.println(temp);
        }
    }

    //修改节点信息
    public void upd(Node node) {
        if (head.nextNode == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head;
        boolean flag = false;
        while (temp.nextNode != null) {
            if (temp.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.nextNode;
        }
        if (flag) {
            temp.name = node.name;
        } else {
            System.out.printf("更新的%d账号不存在\n", node.no);
        }
    }

    //删除节点
    public void del(Node node) {
        if (head.nextNode == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head;
        boolean flag = false;
        //temp 为要删除节点的上一个节点
        while (temp.nextNode != null) {
            if (temp.nextNode.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.nextNode;
        }
        if (flag) {
            //把要删除节点的上一个节点的，下指针指向删除节点的下一个节点
            temp.nextNode = temp.nextNode.nextNode;
        } else {
            System.out.printf("删除的%d账号不存在\n", node.no);
        }
    }

    //有效节点个数
    public int currentSize() {
        int size = 0;
        Node temp = head;
        while (temp.nextNode != null) {
            size++;
            temp = temp.nextNode;
        }
        return size;
    }


    //查询单链表中的倒数第k个节点,自己的思路
    public Node getLastNodeByIndex1(int k) {
        if (k < 0) {
            System.out.println("输入有误");
            return null;
        }
        //获取总的节点数
        int i = currentSize();
        if (k > i) {
            System.out.println("没有那么多节点");
            return null;
        }
        Node temp = head;
        for (int l = 0; l <= i - k; l++) {
            temp = temp.nextNode;
        }
        return temp;

    }

    //双指针
    public Node getLastNodeByIndex2(int k) {
        if (k < 0) {
            System.out.println("输入有误");
            return null;
        }
        //获取总的节点数
        int i = currentSize();
        if (k > i) {
            System.out.println("没有那么多节点");
            return null;
        }

        //当index到末尾时候，index就到指定位置了
        int indexTrue = 0;
        int index = indexTrue + k - 1;


        Node temp = head;
        for (int l = 0; l < (k - 1); l++) {
            temp = temp.nextNode;
        }
        return temp;

    }

    //反转单链表
    public Node resverNode(Node inNode) {
        Node node = new Node();
        return node;
    }

    ;

    //获得链表
    public Node getNode() {
        return this.head;
    }

}

//节点
class Node {
    public int no;
    public String name;
    /**
     * 默认null
     **/
    public Node nextNode;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public Node(int no) {
        this.no = no;
    }

    public Node() {
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' + '}';
    }

    public Node swapNodes(Node head, int k) {
        int sum = 1;
        while (head.nextNode != null) {
            sum++;
            head = head.nextNode;
        }
        int temp = 1;
        int per = 0;
        int tail = 0;
        while (head.nextNode != null) {
            if (temp == k) {
                per = head.no;
            }
            if (temp == sum - k) {
                tail = head.no;
                head.no = per;
            }
            head = head.nextNode;
        }
        while (head.nextNode != null) {
            if (temp == k) {
                head.no = per;
            }
            head = head.nextNode;
        }

        return head;

    }
}




